Home

Download

Support

Developers

Searched: \.*
Results from Stratego web
ACoreLanguageForRewriting (06 Dec 2001 - 17:36 - NEW - EelcoVisser)
E. Visser and Z.-e.-A. Benaissa. A core language for rewriting. In C. Kirchner and H. Kirchner, editors, Second International Workshop on Rewriting Logic and its Applications (WRLA'98), volume 15 of Electronic Notes in Theoretical Computer Science, Pont-à-Mousson, France, September 1998. Elsevier Science Publishers.

Abstract

System S is a calculus providing the basic abstractions of term rewriting: matching and building terms, term traversal, combining computations and handling failure. The calculus forms a core language for implementation of a wide variety of rewriting languages, or more generally, languages for specifying tree transformations. In this paper we show how a conventional rewriting language based on conditional term rewriting can be implemented straightforwardly in System S. Subsequently we show how this implementation can be extended with features such as matching conditions, negative conditions, default rules, non-strictness annotations and alternative evaluation strategies.

Download

CategoryPaper
ATermLibrary (08 Feb 2004 - 18:04 - r1.2 - MartinBravenboer)
AbstractSyntax (17 May 2003 - 19:56 - NEW - MartinBravenboer)
An abstract syntax is a representation of a source code (or data in general) that is independent of the representation of the program in source code, called the concrete syntax.

Typically an abstract syntax for a programming language doesn't contain any layout information and comments. The set of valid abstract syntax trees is the abstract syntax of a language. In the Stratego language the abstract syntax of a language is described by algebraic signatures.

AbstractSyntaxTree (09 Mar 2004 - 13:07 - r1.2 - MartinBravenboer)

Description

An abstract syntax tree is a tree representation of a source program. It abstracts more from the source program than a parse tree?. Usually it doesn't contain layout information and comments.

In StrategoXT the ATerm? format is used to exchange abstact syntax trees between transformation tools. Stratego signatures desribe the abstract syntax of a language.

Example

The expression 1 + 2 * a might be represented in an abstract syntax tree in the ATerm format as: 

  Plus(
    Int("1")
  , Mul(
      Int("2")
    , Var("a")
    )
  )

As a more interesting example consider the following Tiger program: 

  let function fact(n : int) : int =
        if n < 1 then 1 else (n * fact(n - 1))
   in printint(fact(10))
  end

In the Tiger compiler this program is represented as: 

  Let(
    [ FunDecs(
      [ FunDec("fact", [FArg("n",Tp(Tid("int")))]
        , Tp(Tid("int"))
        , If(
            Lt(Var("n"), Int("1"))
          , Int("1")
          , Seq([
              Times(Var("n"), Call(Var("fact"),[Minus(Var("n"),Int("1"))]))
            ])
          )
        )
      ])
    ]
  ,[ Call(
       Var("printint")
     , [ Call(Var("fact"),[Int("10")]) ]
     )
    ]
  )
AddingConcreteSyntaxToAPrologBasedProgramSynthesisSystem (08 May 2004 - 21:45 - r1.3 - EelcoVisser)
B. Fischer and E. Visser. Adding concrete syntax to a Prolog-based program synthesis system (extended abstract). In M. Bruynooghe, editor, Preliminary proceedings of the International Symposium on Logic-based Program Synthesis and Transformation (LOPSTR'03), Uppsala, Sweden, August 2003. (pdf)

This paper is subsumed by the paper 'Retrofitting the AutoBayes program synthesis system with concrete syntax'

Abstract

Program generation and transformation systems manipulate large, parameterized object language fragments. Support for user-definable concrete syntax makes this easier but is typically restricted to certain object and meta languages. We show how Prolog can be retrofitted with concrete syntax and describe how a seamless interaction of concrete syntax fragments with an existing ``legacy'' meta-programming system based on abstract syntax is achieved. We apply the approach to gradually migrate the schemas of the AutoBayes program synthesis system to concrete syntax. First experiences show that this can result in a considerable reduction of the code size and an improved readability of the code. In particular, abstracting out fresh-variable generation and second-order term construction allows the formulation of larger continuous fragments and improves the ``locality'' in the schemas.

Links

Stratego Emacs Mode

The Stratego Emacs Mode provides basic syntax-highlighting for Stratego in Emacs. For installation instructions, see Stratego Emacs Mode.

Available at:

Stratego for NEdit, Vim, Ultraedit

Available at:

Stratego/XT

Stratego/XT Utilities

A bundle of additional utils for Stratego/XT developers (currently, mostly Dot related)

Releases:

XDoc

XDoc is a documentation generator for Stratego.

Stratego Shell

The Stratego Shell implements a Stratego interpreter and an interactive shell for Stratego programming. The interpreter and shell are very useful for learning Stratego and for implementing small tests.

Releases:

C and C++

Transformers

The Transformers Project is developing a program transformation framework for C and C++, based on Stratego/XT. The latest release provides an ambiguous C and C++ syntax definition and separate disambiguation tools for C (complete) and C++ (partial).

Java

Java-front

Java-front adds support for Java program transformation to Stratego/XT. It provides a handcrafted SDF syntax definition and pretty-printer for Java (J2SE 5.0).

Releases:

AspectJ-front

AspectJ-front defines the syntax of AspectJ by extending the Java syntax definition of Java-front.

Jimple-front

Jimple-front defines the syntax of Jimple, the typed 3-address representation of Java bytecode of the Soot Java optimization framework. This representation is suitable for program optimization and analysis.

Dryad

Dryad is a set tools for semantic analysis of Java. It also provides support for working with Java bytecode in Stratego.

PHP

PHP-front

PHP-front provides a syntax definition, parser, pretty-printer, reflection library, and common strategies for PHP.

SQL

SQL-front provides a syntax definition for SQL92.

Prolog

Prolog-tools is a toolset for transforming Prolog programs.

CategoryInstallation

The released versions of BibtexTools are currently not available. You can check out the sources directly from

Released November 4th, 2005

License

BibTeX Tools is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

News

Version 0.2 is the first official release of the Stratego/XT BibTeX Tools package. It is based on Stratego/XT 0.16 and requires Hevea 1.07, a tool for translating latex to html.

Among the useless things one can do in life, maintaining one or more publication lists ranks high. My tendency to waste time on my publication list probably dates back to my days as a PhD student when I badly needed publications to put on a list. On the other hand, as publications are the measure of achievement in research, more researchers may have this problem.

Anyway, maintaining a list of publications can be quite tedious, in particular if you want to provide multiple views on the publications. For example, a listing with most recent publications first, one providing the most important ones first, one organized by research topic, and finally a separate list for each project. Also your department may require regular submission of lists. On the web version the entries should come with links to the pdf files and/or the webpage of the publisher, but these links should not be displayed in the version for printing, since they are quite useless there.

Being a computer scientist, I elevated the activity of maintaining content to maintaining a program for generating the various lists. This is still a waste of time, of course, but the excuse is that it will save me time in future. Another excuse is that I developed my program as a case study for the transformation language Stratego.

In fact, the bibtex-tools package has emerged over a long time, starting with a syntax definition for BibTeX first written in 1999. It turns out that BibTeX has quite an intricate syntax that is not so easily formalized with a traditional approach based on a separate lexical analyzer and context-free parser. With the scannerless approach of SDF this poses no problems at all.

Also, the use of the Stratego to perform transformations on a structured representation of a BibTeX file is a definite improvement over directly transforming its text representation. Moreover, these transformations can be expressed quite concisely. For example, the following strategy definitions define an inliner for BibTeX that replaces occurrences of string identifiers with their body. (BibTeX allows the definition of strings such as @string{LNCS={Lecture Notes in Computer Science}}, which can then be quoted in entry fields using the identifier, e.g., series = LNCS.) 

  bib-inline = 
    bottomup(try(DeclareInlineString + InlineString + FoldWords))x

  DeclareInlineString =
    ?String(_, StringField(key, value))
    ; rules( InlineString : Id(key) -> value )

  FoldWords :
    ConcValue(Words(ws1), Words(ws2)) -> Words((ws1, ws2))

After having developed my own set of BibTeX tools using the Stratego transformation language over the last couple of years, I decided to make them into a proper software package that could be used by others, complete with a manual that explains the LaTeX/BibTeX/Hevea techniques used to get a publication list into HTML.

More Information

See the website of BibTeX Tools for an overview of the development, and introduction, examples, and a manual for BibTeX Tools.

BoundUnboundVariableAnalysis (17 Aug 2003 - 13:21 - NEW - EelcoVisser)
The bound-unbound-vars component of the Stratego optimizer annotates variables with one of the annotations "bound", "unbound", or "(un)bound", with the following meanings:

  • ="bound=" : the variable has been bound in a previous match
  • ="unbound=" : the variable has been declared in a scope, but is not yet bound in a match
  • "(un)bound" : the variable may or may not be bound

Variables are bound in matches, used in builds, and refreshed in scopes. Choice operators may lead to a variable being bound in one path, but not in the other. Such variables are annotated with "(un)bound".

This analysis is used in the StrategoFrontEnd for use def analysis?, in the optimizer for dead variable elimination, and in the back-end to avoid run time checks on variables.

-- EelcoVisser - 17 Aug 2003

BreadthFirstTraversal (06 Jan 2002 - 16:34 - r1.2 - EelcoVisser)
JoostVisser and I have looked at a breadth first for Tools.JJTraveler. The breadth first in the Stratego library is incorrect:
  • It doesn't apply s to the root (and hence not to any node);
  • It's not overall breadht-first, only breadth-first per node.
-- ArieVanDeursen; 25 Nov 2001.

It is indeed not a correct implementation of breadth first, but it does actually apply transformations. Consider the definition: 

  breadth-first(s) = 
    rec x(all(s); all(x))
This first applies s to all direct subterms of the root, and then recursively applies x to the direct sub-terms. The difference with topdown is that all subterms are visited, before visiting subterms recursively. What is a better name for this strategy? kids-first maybe?

An implementation of proper breadth-first should employ a global queue data structure to which terms to be visited should be added. It is also interesting to consider using TermAnnotation to let a term point to the next term in a breadth-first traversal.

-- EelcoVisser - 09 Dec 2001

CategoryToDo? | ToDo | LibraryImprovements
BuildMatchFusion (18 Aug 2003 - 20:16 - NEW - EelcoVisser)
The composition of a match and a build (in either order) can often be simplified. If the match following a build is incompatible, failure is certain. For example, 
  !Foo(Bar(x), y); ?FooBar(z)
can be replaced with fail since the match will never succeed.

If the build and match are compatible (i.e., if they can be unified), the sequence can be simplified. For example, 

  !Foo(Bar(x), y); ?Foo(z1, z2); ...
can be replaced with 
  !Bar(x); ?z1; !y; ?z2; !Foo(Bar(x), y); ...
Subsequent transformations can get rid of the construction of the entire term, if it is not needed.

These ideas are implemented by simple rewrite rules in module

The rules are applied by the Stratego simplifier. Often these rules are triggered by inlining (which brings matches and builds together). The results are simplified by constant and copy propagation and dead variable elimination.

-- EelcoVisser - 18 Aug 2003

BuildfarmConfiguration (11 May 2008 - 11:28 - r1.5 - KarlTrygveKalleberg)
To add a job, you need to:

  1. describe your package in packages.nix (e.g. fooFront)
  2. add a release to releases.nix (e.g. fooFrontUnstable), referring to fooFront in packages.nix
  3. add a job to the buildfarm jobs.nix (e.g. fooFrontTrunk), referring to fooFront in packages.nix

Pointers

Package Descriptions

See the other package descriptions for examples. Important are:

  • packageName (e.g. "foo-front")
  • attrPrefix (e.g. "fooFront")
  • contactEmail
  • notifyAddresses (non-empty list of email addresses)
  • svn, with usually a trunk attribute
  • requires (e.g. [aterm sdf2Bundle strategoxt])
    • Dependencies on other packages that are being built in this buildfarm. The exact package to built against will be determined by the inputs of the build job, which are links to release-info.xml.
  • svnRequires (e.g. requires)
  • buildInputs (e.g. [pkgs.pkgconfig])
    • dependencies from nixpkgs, not being built in this buildfarm
  • svnBuildInputs
    • stuff needed when building from svn, not being built in this buildfarm
  • systemSupported (e.g. systemSupport pkgs commonSystemsSupported)

Make sure that the file is syntactically correct before committing: packages.nix is imported by the jobs configuration. If there is a syntactic problem in packages.nix, then the entire buildfarm will go down. You can use nix-instantiate to check the syntax of packages.nix, or (better) you can evaluate the entire jobs.nix file (see Jobs).

Releases

Just copy one of the examples.

Jobs

This file is somewhat documented. Adding a job without strange dependencies should be fairly easy.

Make sure to check if the job you added is syntactically correct, otherwise the entire buildfarm will go down. For that, instantiate the main jobs.nix file (which is one level up from the strategoxt directory). 

$ pwd
/home/martin/wc/supervisor/strategoxt

$ /nix/bin/nix-instantiate ../jobs.nix --eval-only --strict --xml

You can also test your job. First you have check out a couple of directories: 

$ svn co https://svn.nixos.org/repos/nix/release/trunk release
$ svn co https://svn.nixos.org/repos/nix/configurations/trunk/tud/buildfarm

After this, you must update the file release/jobs/strategoxt/test/generate-test.sh and make it point to the release directory you checked out. After this, you're ready to start building: 

$ cd release/jobs/strategoxt/test
$ ./generate-test.sh fooFrontTrunk
$ ./fetch-inputs.sh
$ nix-build test.nix

where fooFrontTrunk should be substitued with your favourite package.

Configuration

Want something else?

If you don't want to use the system of packages.nix and dependencies on releases produced by the buildfarm, then you can take a look at the Nix jobs:

BuildingInterpretersWithRewritingStrategies (23 May 2002 - 12:08 - r1.3 - EelcoVisser)
EelcoDolstra and EelcoVisser. Building Interpreters With Rewriting Strategies In MarkVanDenBrand and RalfLaemmel (editors) Workshop on Language Descriptions, Tools and Applications (LDTA'02). volume 65.3 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers, April 2002. (To appear)

Abstract

Programming language semantics based on pure rewrite rules suffers from the gap between rewriting strategy implemented in rewriting engines and the intended evaluation strategy. This paper shows how programmable rewriting strategies can be used to implement interpreters for programming languages based on rewrite rules. The advantage of this approach is that reduction rules are first class entities that can be reused in different strategies, even in other kinds of program transformations such as optimizers. The approach is illustrated with several interpreters for the lambda calculus based on implicit and explicit (parallel) substitution, different strategies including normalization, eager evaluation, lazy evaluation, and lazy evaluation with updates. An extension with pattern matching and choice shows that such interpreters can easily be extended.

Preprint

Related

CategoryPaper
BuildingProgramOptimizersWithRewritingStrategies (29 Nov 2003 - 23:41 - r1.3 - EelcoVisser)
E. Visser, Z.-e.-A. Benaissa, and A. Tolmach. Building program optimizers with rewriting strategies. In Proceedings of the third ACM SIGPLAN International Conference on Functional Programming (ICFP'98), pages 13--26. ACM Press, September 1998.

Abstract

We describe a language for defining term rewriting strategies, and its application to the production of program optimizers. Valid transformations on program terms can be described by a set of rewrite rules; rewriting strategies are used to describe when and how the various rules should be applied in order to obtain the desired optimization effects. Separating rules from strategies in this fashion makes it easier to reason about the behavior of the optimizer as a whole, compared to traditional monolithic optimizer implementations. We illustrate the expressiveness of our language by using it to describe a simple optimizer for an ML-like intermediate representation.

The basic strategy language uses operators such as sequential composition, choice, and recursion to build transformers from a set of labeled unconditional rewrite rules. We also define an extended language in which the side-conditions and contextual rules that arise in realistic optimizer specifications can themselves be expressed as strategy-driven rewrites. We show that the features of the basic and extended languages can be expressed by breaking down the rewrite rules into their primitive building blocks, namely matching and building terms in variable binding environments. This gives us a low-level core language which has a clear semantics, can be implemented straightforwardly and can itself be optimized. The current implementation generates C code from a strategy specification.

Preprint

CategoryPaper